// ------------------------------
// projects/c++/integer/Integer.h
// Copyright (C) 2009
// Glenn P. Downing
// ------------------------------

#ifndef Integer_h
#define Integer_h

// --------
// includes
// --------

#include <cassert>   // assert
#include <iostream>  // ostream
#include <stdexcept> // invalid_argument
#include <string>    // string
#include <vector>    // vector

// ----------
// namespaces
// ----------

namespace My {


// -----------
// plus_digits
// -----------

/**
 * @param b1  an iterator to the beginning of an input  sequence (inclusive)
 * @param e1  an iterator to the end       of an input  sequence (exclusive)
 * @param b2 an iterator to the beginning of an input  sequence (inclusive)
 * @param e2 an iterator to the end       of an input  sequence (exclusive)
 * @param x  an iterator to the beginning of an output sequence (inclusive)
 * @return   an iterator to the end       of an output sequence (exclusive)
 * the sequences are of decimal digits
 * output the sum of the two input sequences into the output sequence
 * (s1 + s2) => x
 * takes input sequences in reverse and outputs them in reverse
 */
template <typename II1, typename II2, typename OI>
OI plus_digits (II1 b1, II1 e1, II2 b2, II2 e2, OI x) {	
	bool carry = false;
	int result = 0;
	while( b1 < (e1 + carry) || b2 < (e2 + carry)) {
		int top_digit = (b1 < e1) ? *b1 : 0; int bottom_digit = (b2 < e2) ? *b2 : 0;
		result = carry + top_digit + bottom_digit;
		*x = result % 10;
		carry = result / 10;
		x++; ++b1; ++b2;}
	return x;}

// ------------
// minus_digits
// ------------

/**
 * @param b1  an iterator to the beginning of an input  sequence (inclusive)
 * @param e1  an iterator to the end       of an input  sequence (exclusive)
 * @param b2 an iterator to the beginning of an input  sequence (inclusive)
 * @param e2 an iterator to the end       of an input  sequence (exclusive)
 * @param x  an iterator to the beginning of an output sequence (inclusive)
 * @return   an iterator to the end       of an output sequence (exclusive)
 * Precondition: first sequence is larger number than the second sequence
 * the sequences are of decimal digits
 * output the difference of the two input sequences into the output sequence
 * (s1 - s2) => x
 * input and output sequences are in reverse
 */
template <typename II1, typename II2, typename OI>
OI minus_digits (II1 b1, II1 e1, II2 b2, II2 e2, OI x) {
	OI tempx = x;
	bool borrow = false;
	while( b1 < e1 || b2 < e2) {
		int top_digit = (b1 < e1) ? *b1 : 0; int bottom_digit = (b2 < e2) ? *b2 : 0;

		if(borrow && top_digit == 0)	//secondary borrower
			top_digit = 9;
		else {
			if(borrow)	//the original supplier of the borrow
				--top_digit;
			borrow = top_digit < bottom_digit;
		}
		//(borrow && top_digit != 9)*10 only adds the 10 if truly the receiver of the borrowed digits
		*x = (borrow && top_digit != 9)*10 + top_digit - bottom_digit;
		if(b2 <= e2)
			x++; 
		b1++; b2++;
	}
	while (*(x-1) == 0 && x-1 != tempx)  //fixes extra zeros being padded
		--x;
	return x;}

// -----------------
// multiplies_digits
// -----------------

/**
 * @param b1  an iterator to the beginning of an input  sequence (inclusive)
 * @param e1  an iterator to the end       of an input  sequence (exclusive)
 * @param b2 an iterator to the beginning of an input  sequence (inclusive)
 * @param e2 an iterator to the end       of an input  sequence (exclusive)
 * @param x  an iterator to the beginning of an output sequence (inclusive)
 * @return   an iterator to the end       of an output sequence (exclusive)
 * the sequences are of decimal digits
 * output the product of the two input sequences into the output sequence
 * (s1 * s2) => x
 * the input and output sequences are in reverse
 */
template <typename II1, typename II2, typename OI>
OI multiplies_digits (II1 b1, II1 e1, II2 b2, II2 e2, OI x) {
	std::vector<std::vector<int> > cache ( 10, std::vector<int>(e1-b1+1) );

	for(int i = 1; i < 10; i++)
		plus_digits(cache.at(i-1).begin(), cache.at(i-1).end(), b1, e1, cache.at(i).begin());

	std::vector<int> temp;
	int k = 0;
	*x = 0;
	OI end = x + 1; 
	while(b2 != e2)	{
		temp = cache.at(*b2);
		temp.insert(temp.begin(), k, 0);
		if(*(temp.end() - 1) == 0)
			end = plus_digits(temp.begin(), temp.end() - 1, x, end, x);
		else
			end = plus_digits(temp.begin(), temp.end(), x, end, x);
		b2++; k++;
	}
    return end;}

// --------------
// divides_digits
// --------------

/**
 * @param b1  an iterator to the beginning of an input  sequence (inclusive)
 * @param e1  an iterator to the end       of an input  sequence (exclusive)
 * @param b2 an iterator to the beginning of an input  sequence (inclusive)
 * @param e2 an iterator to the end       of an input  sequence (exclusive)
 * @param x  an iterator to the beginning of an output sequence (inclusive)
 * @return   an iterator to the end       of an output sequence (exclusive)
 * the sequences are of decimal digits
 * output the division of the two input sequences into the output sequence
 * (s1 / s2) => x
 */
template <typename II1, typename II2, typename OI>
OI divides_digits (II1 b1, II1 e1, II2 b2, II2 e2, OI x) {
    // <your code>
 		std::vector<int> dividend;
        II1 tempb = b1;
        while(tempb != e1) {
                dividend.push_back(*tempb);
                ++tempb;
        }

//		print(b2, e2);
        std::vector<int> divisor;
        int shift = (e1-b1) - (e2-b2) - 1;
		for(int i = 0; i < shift; i++)
			divisor.push_back(0);
		II2 tempb2 = b2;
		while(tempb2 != e2) {
			divisor.push_back(*tempb2);
			++tempb2;
		}
        std::vector<int> multiplier(shift, 0);
        multiplier.push_back(1);

        OI end = x+1;
		std::vector<int>::iterator div_begin = dividend.begin();
		std::vector<int>::iterator div_end = dividend.end();
        *x = 0;
        while ( multiplier.size() > 0) {
                div_end = minus_digits(dividend.begin(), div_end, divisor.begin(), divisor.end(), dividend.begin());
				if( unsigned (div_end - div_begin) != dividend.size())
					dividend.resize(div_end - div_begin);
                end = plus_digits(x, end, multiplier.begin(), multiplier.end(), x);

                while(divisor.size() > dividend.size() && multiplier.size() > 0){
                        divisor.erase(divisor.begin()); multiplier.erase(multiplier.begin());
				}
				
                if(divisor.size() == dividend.size()) {
                        for(unsigned int i = 1; i <= divisor.size(); i++) // checks to make sure dividend hasn't become smaller than divisor
                                if(*(divisor.end() - i) > *(dividend.end() - i)) {
                                        divisor.erase(divisor.begin()); multiplier.erase(multiplier.begin());  // = divide by 10
                                        break;
                                }
								else if(*(divisor.end() - i) < *(dividend.end() - i))
									 break;
                }
        }
	
    return end;}

// -----------------
// shift_left_digits
// -----------------

/**
 * @param b  an iterator to the beginning of an input  sequence (inclusive)
 * @param e  an iterator to the end       of an input  sequence (exclusive)
 * @param n  the number of digits to shift the input sequence left by
 * @param x  an iterator to the beginning of an output sequence (inclusive)
 * @return   an iterator to the end       of an output sequence (exclusive)
 * the sequences are of decimal digits
 * output the shift left of the input sequence into the output sequence
 * (s << n) => x
 */
template <typename II, typename OI>
OI shift_left_digits (II b, II e, int n, OI x) {
//	b += n; //ignores unimportant digits
	for(int i = 0; i < n; i++){
		*x = 0;
		++x;
	}
	while (b != e)
	{
		*x = *b;
		++x; ++b;
	}
    return x;}

// ------------------
// shift_right_digits
// ------------------

/**
 * @param b  an iterator to the beginning of an input  sequence (inclusive)
 * @param e  an iterator to the end       of an input  sequence (exclusive)
 * @param n  the number of digits to shift the input sequence right by
 * @param x  an iterator to the beginning of an output sequence (inclusive)
 * @return   an iterator to the end       of an output sequence (exclusive)
 * the sequences are of decimal digits
 * output the shift right of the input sequence into the output sequence
 * (s >> n) => x
 */
template <typename II, typename OI>
OI shift_right_digits (II b, II e, int n, OI x) {
	b += n; //ignores unimportant digits
	if(b >= e)	{
		*x = 0;
		return x + 1;
	}
	while (b != e)
	{
		*x = *b;
		++x; ++b;
	}
    return x;}

// -------
// Integer
// -------

template < typename T, typename C = std::vector<T> >
class Integer {
    public:
        // -----------
        // operator ==
        // -----------

    	/**
    	 * @param  lhs an address of the Integer on the left side
    	 * @param  rhs an address of the Integer on the right side
    	 * @return true if the values of the Integers are equal
    	 */
        friend bool operator == (const Integer& lhs, const Integer& rhs) {
            // <your code>
			int diff = (lhs.container.end() - lhs.container.begin()) - (rhs.container.end() - rhs.container.begin());
			if(diff != 0)
				return false;
			if ( lhs.negative != rhs.negative)
				return false;
			for(int i = 0; i < lhs.container.end() - lhs.container.begin(); ++i){
				if(*(lhs.container.begin() + i) != *(rhs.container.begin() + i))
					return false;
			}
            return true;}

        // -----------
        // operator !=
        // -----------

        /**
         * @param  lhs an address of the Integer on the left side
         * @param  rhs an address of the Integer on the right side
         * @return true if the values of the Integers are not equal
         */
        friend bool operator != (const Integer& lhs, const Integer& rhs) {
            return !(lhs == rhs);}

        // ----------
        // operator <
        // ----------

        /**
         * @param  lhs an address of the Integer on the left side
         * @param  rhs an address of the Integer on the right side
         * @return true if the values of the Integers on the left is smaller.
         */
        friend bool operator < (const Integer& lhs, const Integer& rhs) {
            // <your code>
			if(rhs.negative && !lhs.negative)
				return false;
			if(!rhs.negative && lhs.negative)
				return true;
			bool neg = false;
			if(rhs.negative && lhs.negative)
				neg = true;

			int diff = (lhs.container.end() - lhs.container.begin()) - (rhs.container.end() - rhs.container.begin());
			if(diff > 0)
				return neg ? true : false;
			if(diff < 0)
				return neg ? false : true;
			for(int i = 1; i <= lhs.container.end() - lhs.container.begin(); ++i){
				if(neg){
					if(*(lhs.container.end() - i) <= *(rhs.container.end() - i))
						return false;	}
				else
					if(*(lhs.container.end() - i) >= *(rhs.container.end() - i))
						return false;
			}
            return true;}

        // -----------
        // operator <=
        // -----------

        /**
         * @param  lhs an address of the Integer on the left side
         * @param  rhs an address of the Integer on the right side
         * @return true if the values of the Integers on the left is smaller or equal.
         */
        friend bool operator <= (const Integer& lhs, const Integer& rhs) {
            return !(rhs < lhs);}

        // ----------
        // operator >
        // ----------

        /**
         * @param  lhs an address of the Integer on the left side
         * @param  rhs an address of the Integer on the right side
         * @return true if the values of the Integers on the left is larger.
         */
        friend bool operator > (const Integer& lhs, const Integer& rhs) {
            return (rhs < lhs);}

        // -----------
        // operator >=
        // -----------

        /**
         * @param  lhs an address of the Integer on the left side
         * @param  rhs an address of the Integer on the right side
         * @return true if the values of the Integers on the left is larger or equal.
         */
        friend bool operator >= (const Integer& lhs, const Integer& rhs) {
            return !(lhs < rhs);}

        // ----------
        // operator +
        // ----------

        /**
         * @param  lhs Integer on the left side
         * @param  rhs a referenece of the Integer on the right side
         * @return an Integer of the value of the two Integers added together
         */
        friend Integer operator + (Integer lhs, const Integer& rhs) {
            return lhs += rhs;}

        // ----------
        // operator -
        // ----------

        /**
         * @param  lhs Integer on the left side
         * @param  rhs a referenece of the Integer on the right side
         * @return an Integer of the value of the difference between the two Integers
         */
        friend Integer operator - (Integer lhs, const Integer& rhs) {
            return lhs -= rhs;}

        // ----------
        // operator *
        // ----------

        /**
         * @param  lhs Integer on the left side
         * @param  rhs a referenece of the Integer on the right side
         * @return an Integer of the value of the product between the two Integers
         */
        friend Integer operator * (Integer lhs, const Integer& rhs) {
            return lhs *= rhs;}

        // ----------
        // operator /
        // ----------

        /**
         * @param  lhs Integer on the left side
         * @param  rhs a reference of the Integer on the right side
         * @return an Integer of the value of the dividend between the two Integers
         * @throws invalid_argument if (rhs == 0)
         */
        friend Integer operator / (Integer lhs, const Integer& rhs) {
        	if ( rhs == 0)
        		throw std::invalid_argument("Integer::operator/(Integer, Integer&)");
            return lhs /= rhs;}

        // ----------
        // operator %
        // ----------

        /**
		 * @param  lhs Integer on the left side
		 * @param  rhs a reference of the Integer on the right side
		 * @return an Integer of the value of the modulus between the two Integers
         * @throws invalid_argument if (rhs <= 0)
         */
        friend Integer operator % (Integer lhs, const Integer& rhs) {
           	if ( rhs <= 0)
            		throw std::invalid_argument("Integer::operator*(Integer, Integer&)");
            return lhs %= rhs;}

        // -----------
        // operator <<
        // -----------

        /**
         * @param  lhs Integer on the left side
         * @param  rhs an int of hows many times the Integer is to be shifted to the left
         * @return an Integer, lhs shifted to the left rhs times
         */
        friend Integer operator << (Integer lhs, int rhs) {
            return lhs <<= rhs;}

        // -----------
        // operator >>
        // -----------

        /**
         * @param  lhs Integer on the left side
         * @param  rhs an int of hows many times the Integer is to be shifted to the right
         * @return an Integer, lhs shifted to the right rhs times
         */
        friend Integer operator >> (Integer lhs, int rhs) {
            return lhs >>= rhs;}

        // -----------
        // operator <<
        // -----------

        /**
         * @param  lhs a reference of the ostream
         * @param  rhs a reference of an Integer
         * @return an ostream containing the Integer
         */
        friend std::ostream& operator << (std::ostream& lhs, const Integer& rhs) {
            // <your code>
			if( rhs.negative)
				lhs << "-";
			for(int i = 1; i <= rhs.container.end() - rhs.container.begin(); ++i)
				lhs << *(rhs.container.end() - i);

            return lhs;}

    private:
        // ----
        // data
        // ----

        // <your data>
		C container;
		bool negative;

        // -----
        // valid
        // -----

        bool valid () const {
            // <your code>
			for(int i = 0; i < container.end()-container.begin(); i++)
				if( *(container.begin() + i) < 0 || *(container.begin() + i) > 9)
					return false;
            return true;}

    public:
        // ------------
        // constructors
        // ------------

        /**
         * Integer constructor
         * @param value integer input for Integer constructor 
         */
        Integer (int value) {
            // <your code>
			negative = value < 0;
			if(negative) value *= -1;
			if(value == 0) container.push_back(0);
			else
				while(value > 0){
					container.push_back(value % 10);
					value /= 10;
				}
            assert(valid());}

        /**
         * Integer constructor
         * @param value string input of an integer 
         * @throws invalid_argument if value is not a valid representation of an Integer
         */
        explicit Integer (const std::string& value) {
            // <your code>
            int s = value.size();
			negative = value[0] == '-' ? true : false;
			int i = negative ? 1 : 0;
			for(; s > i; --s) {
				int number = value[s - 1] - '0';
					container.push_back(number);
			}
            if (!valid())
                throw std::invalid_argument("Integer::Integer()");}


        // Default copy, destructor, and copy assignment.
        // Integer (const Integer&);
        // ~Integer ();
        // Integer& operator = (const Integer&);

        // ----------
        // operator -
        // ----------

        /** 
         * Unary minus operator
         * @return new negated Integer
         */
        Integer operator - () const {
            // <your code>
			Integer neg = *this;
			neg.negative = !neg.negative;
            return neg;}

        // -----------
        // operator ++
        // -----------

        /**
         * Pre-increment operator
         * @return incremented Integer
         */
        Integer& operator ++ () {
            *this += 1;
            return *this;}

        /**
         * Post-increment operator
         * @return Integer
         */
        Integer operator ++ (int) {
            Integer x = *this;
            ++(*this);
            return x;}

        // -----------
        // operator --
        // -----------

        /**
         * Pre-decrement operator
         * @return decremented Integer
         */
        Integer& operator -- () {
            *this -= 1;
            return *this;}

        /**
         * Post-decrement operator
         * @return Integer
         */
        Integer operator -- (int) {
            Integer x = *this;
            --(*this);
            return x;}

        // -----------
        // operator +=
        // -----------

        /**
         * Plus Equals operator
         * @param rhs const Integer& of Integer to add to current value
         * @return Integer& of modified Integer 
         */
        Integer& operator += (const Integer& rhs) {
            // <your code>

        	int size = (container.size() > rhs.container.size()) ? container.size() + 1 : rhs.container.size() + 1;
        	C temp(size);
        	typename C::iterator end;
        	if(negative == rhs.negative)
        		end = plus_digits(container.begin(), container.end(), rhs.container.begin(), rhs.container.end(), temp.begin());
        	else
				if( abs() > rhs.abs() ) 
	        		end = minus_digits(container.begin(), container.end(), rhs.container.begin(), rhs.container.end(), temp.begin());
				else {
					end = minus_digits(rhs.container.begin(), rhs.container.end(), container.begin(), container.end(), temp.begin());
					negative = (!negative);
				 }

        	container.assign(temp.begin(), end);

            return *this;}

        // -----------
        // operator -=
        // -----------

        /**
         * Minus Equals operator
         * @param rhs const Integer& of Integer to subtract from current value
         * @return Integer& of modified Integer 
         */
        Integer& operator -= (const Integer& rhs) {
            // <your code>
			if (rhs == 1 && (*container.begin() != 0)){
				--(*container.begin());
				return *this;
			}
			else
            return *this += -rhs;}
        // -----------
        // operator *=
        // -----------

        /**
         * Times Equals operator
         * @param rhs const Integer& of Integer to multiply current value by
         * @return Integer& of modified Integer 
         */
        Integer& operator *= (const Integer& rhs) {
            // <your code>
        	C temp(container.end()-container.begin()+rhs.container.end()-rhs.container.begin());
        	typename C::iterator end = multiplies_digits(container.begin(), container.end(), rhs.container.begin(), rhs.container.end(), temp.begin());
        	container.assign(temp.begin(), end);
        	negative = negative ^ rhs.negative;
            return *this;}

        // -----------
        // operator /=
        // -----------

        /**
         * Divide Equals operator
         * @param rhs const Integer& of Integer to divide current value by
         * @return Integer& of modified Integer
         * @throws invalid_argument if (rhs == 0)          
         */
        Integer& operator /= (const Integer& rhs) {
            // <your code>
                if(rhs == 0)
                        throw std::invalid_argument("Integer::operator/=(const Integer&)");
                C temp(container.end() - container.begin());
                typename C::iterator end = divides_digits(container.begin(), container.end(), rhs.container.begin(), rhs.container.end(), temp.begin());
                container.assign(temp.begin(), end);
                negative = negative ^ rhs.negative;
            return *this;}

        // -----------
        // operator %=
        // -----------

        /**
         * Mod Equals
         * @param rhs const Integer& of Integer to mod current value by
         * @return Integer& of modified Integer
         * @throws invalid_argument if (rhs <= 0)
         */
        Integer& operator %= (const Integer& rhs) {
            // <your code>
                if(rhs.negative)
                                throw std::invalid_argument("Integer::operator%=(const Integer&)");
                Integer temp = (*this) - ((*this / rhs)*(*this));
                container = temp.container;
                negative = false;
            return *this;}

        // ------------
        // operator <<=
        // ------------

        /**
         * Shift Left Equals
         * @param n int to shift current value left by
         * @return Integer& of modified Integer
         */
        Integer& operator <<= (int n) {
            // <your code>
        	C temp(container.end()-container.begin()+n);
        	shift_left_digits(container.begin(), container.end(), n, temp.begin());
        	container = temp;
            return *this;}

        // ------------
        // operator >>=
        // ------------

        /**
         * Shift Right Equals
         * @param n int to shift current value right by
         * @return Integer& of modified Integer
         */
        Integer& operator >>= (int n) {
            // <your code>
        	int size = container.end()-container.begin()-n;
        	if (size < 1)
        		size = 1;
        	C temp(size);
        	shift_right_digits(container.begin(), container.end(), n, temp.begin());
        	container = temp;
            return *this;}

        // ---
        // abs
        // ---

        /**
         * absolute value
         * @return Integer absolute value of current Integer
         */
        Integer abs () const {
            // <your code>
			Integer absolute = *this;
			absolute.negative = false;
            return absolute;}

        // ---
        // pow
        // ---

        /**
         * power
         * @param e int value of exponent
         * @return Integer value of current value raised to the power of argument e
         * @throws invalid_argument if (this == 0) && (e == 0)
         * @throws invalid_argument if (e < 0)
         */
        Integer pow (int e) const {
            // <your code>
        	if((*this == 0 && e == 0) || e < 0)
        		throw std::invalid_argument("Integer::pow()"); 
			if( e == 0 )
				return Integer(1);
			int copy = e;
			int iterations = 0;
			int back = 1;
			while(copy != 1) {
				copy /= 2;
				++iterations;
				back *= 2;
			}
			Integer power = *this;
			for(int i = 0; i < iterations; ++i) {
				power *= power;
			}
			int i = back;
        	for (; i < e; ++i) {
				power *= *this;
        	}
            return power;}};

} // My

#endif // Integer_h

